import java.security.Key;
import java.util.Objects;

class Person {
	public String id ;

	public Person(String id) {
		this.id = id;
	}

	/**
	 * TreeSet和TreeMap底层是一个搜索树，当我们在插入元素的时候，我们需要告知他们的比较方式
	 * 当是基本的引用数据类型的时候，不需要重写hascode和equals
	 * @param o
	 * @return
	 */
	@Override
	public boolean equals(Object o) {
		if (this == o) return true;
		if (o == null || getClass() != o.getClass()) return false;
		Person person = (Person) o;
		return Objects.equals(id, person.id);
	}

	@Override
	public int hashCode() {
		return Objects.hash(id);
	}
}
public class HashBuck1<K,V> {
	static class Node <K,V> {
		public K key;
		public V val;
		public Node<K,V> next;

		public Node(K key, V val) {
			this.key = key;
			this.val = val;
		}
	}
	public Node<K,V>[] array;
	public int usedSize;

	public HashBuck1() {
		array = (Node <K,V> [] )new Node[10];
	}

	public void put(K key, V val) {
		int hash=key.hashCode();
		int index=hash%array.length;
		//哈希表的话，如果存在的话，就需要更新它的val值
		//不存在的话，就需要插入这个的值
		Node<K,V> cur=array[index];
		while(cur!=null) {
			if(cur.key.equals(key)) {
				cur.val=val;
				return ;
			}
			cur=cur.next;
		}
		//程序走到这里说明没有这个key
		Node<K,V> node=new Node<K,V>(key,val);
		node.next=array[index];
		array[index]=node;
		usedSize++;
		if(loadFactor()>0.75) {
			resize();
		}
	}
	private void resize() {
		Node<K,V> [] tempArr=(Node<K,V>[])new Node [array.length*2];
		for(int i=0;i<array.length;i++) {
			Node<K,V> cur=array[i];
			while(cur!=null) {
				//先记录下来下一个节点
				Node<K,V> curNext=cur.next;
				int hash=cur.key.hashCode();
				int index=hash% tempArr.length;
				//进行头插
				cur.next=tempArr[index];
				tempArr[index]=cur;
				cur=curNext;
			}
		}
		array=tempArr;
	}
	private double loadFactor() {
		return usedSize*1.0/this.array.length;
	}
	public V get(K key) {
		int hash=key.hashCode();
		int index=hash%array.length;
		Node<K,V> cur=array[index];
		while(cur!=null) {
			if(cur.key.equals(key)) {
				return cur.val;
			}
			cur=cur.next;
		}
		return null;
	}
}
